package com.cqs.leetcode;

import java.util.LinkedHashMap;
import java.util.Map;

public class RegularExpressionMatching10 {

    /**
     * 注意边界的处理
     * 特别要注意数组越界的情况
     *
     * @param s
     * @param p
     * @return
     */
    public boolean isMatch(String s, String p) {
        if (s == null && p == null) return true;
        if (s == null || p == null) return false;
        if (s.length() > 0 && "".equals(p)) return false;
        //边界问题
        if (s.equals("")) {
            while (p.length() > 1 && p.charAt(p.length() - 1) == '*') {
                p = p.substring(0, p.length() - 2);
            }
            return "".equals(p);
        }
        //从尾部开始匹配
        int si = s.length() - 1;
        int pi = p.length() - 1;
        char c = p.charAt(pi);
        switch (p.charAt(pi)) {
            case '*':
                --pi;
                c = p.charAt(pi);

                final String sp = p.substring(0, pi);
                //0个或者多个c
                do {
                    boolean match = isMatch(s.substring(0, si + 1), sp);
                    if (match) return true;
                    --si;
                } while (si >= -1 && (c == '.' || s.charAt(si + 1) == c));//.*的情况需要将s及s的所有字串和sp进行比较
                //c* 需要将 s.charAt(si + 1)等于c的所有子串与sp进行比较


                return false;
            case '.':
                return isMatch(s.substring(0, si), p.substring(0, pi));
            default:
                return s.charAt(si) == c && isMatch(s.substring(0, si), p.substring(0, pi));
        }
    }

    //DP
    public boolean isMatchDP(String s, String p) {
        if (s == null || p == null) {
            return false;
        }
        int sl = s.length();
        int pl = p.length();
        boolean[][] dp = new boolean[sl + 1][pl + 1];
        dp[0][0] = true;

        for (int i = 1; i < pl; i++) {
            if (p.charAt(i) == '*' && dp[0][i - 1]) {
                dp[0][i + 1] = true;
            }
        }
        for (int i = 0; i < sl; i++) {
            for (int j = 0; j < pl; j++) {
                if (j >= 1 && p.charAt(j) == '*') {
                    //dp[i][j - 1] 表示使用0个
                    dp[i + 1][j + 1] = dp[i + 1][j - 1] || dp[i + 1][j] || (dp[i][j + 1] && (s.charAt(i) == p.charAt(j - 1) || p.charAt(j - 1) == '.'));
                } else {
                    dp[i + 1][j + 1] = dp[i][j] && (p.charAt(j) == '.' || s.charAt(i) == p.charAt(j));
                }
            }
        }
        return dp[sl][pl];
    }


    //递归 --leetcode
    static class Solution {
        public boolean isMatch(String text, String pattern) {
            if (pattern.isEmpty()) return text.isEmpty();
            boolean first_match = (!text.isEmpty() &&
                    (pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.'));

            if (pattern.length() >= 2 && pattern.charAt(1) == '*') {
                return (isMatch(text, pattern.substring(2)) ||
                        (first_match && isMatch(text.substring(1), pattern)));
            } else {
                return first_match && isMatch(text.substring(1), pattern.substring(1));
            }
        }
    }

    //DP
    class Solution2 {

        //        Bottom-Up Variation
        public boolean isMatch(String s, String p) {

            if (s == null || p == null) {
                return false;
            }
            boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
            dp[0][0] = true;
            for (int i = 0; i < p.length(); i++) {
                if (p.charAt(i) == '*' && dp[0][i - 1]) {
                    dp[0][i + 1] = true;
                }
            }
            for (int i = 0; i < s.length(); i++) {
                for (int j = 0; j < p.length(); j++) {
                    if (p.charAt(j) == '.') {
                        dp[i + 1][j + 1] = dp[i][j];
                    }
                    if (p.charAt(j) == s.charAt(i)) {
                        dp[i + 1][j + 1] = dp[i][j];
                    }
                    if (p.charAt(j) == '*') {
                        if (p.charAt(j - 1) != s.charAt(i) && p.charAt(j - 1) != '.') {
                            dp[i + 1][j + 1] = dp[i + 1][j - 1];
                        } else {
                            dp[i + 1][j + 1] = (dp[i + 1][j] || dp[i][j + 1] || dp[i + 1][j - 1]);
                        }
                    }
                }
            }
            return dp[s.length()][p.length()];
        }

        public boolean isMatch_r(String text, String pattern) {
            boolean[][] dp = new boolean[text.length() + 1][pattern.length() + 1];
            dp[text.length()][pattern.length()] = true;

            for (int i = text.length(); i >= 0; i--) {
                for (int j = pattern.length() - 1; j >= 0; j--) {
                    boolean first_match = (i < text.length() &&
                            (pattern.charAt(j) == text.charAt(i) ||
                                    pattern.charAt(j) == '.'));
                    if (j + 1 < pattern.length() && pattern.charAt(j + 1) == '*') {
                        dp[i][j] = dp[i][j + 2] || first_match && dp[i + 1][j];
                    } else {
                        dp[i][j] = first_match && dp[i + 1][j + 1];
                    }
                }
            }
            return dp[0][0];
        }
    }

    // Top-Down Variation
    static class Solution3 {


        public boolean isMatch(String s, String p) {
            if (s == null || p == null) {
                return false;
            }
            boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
            dp[0][0] = true;
            for (int i = 0; i < p.length(); i++) {
                if (p.charAt(i) == '*' && dp[0][i - 1]) {
                    dp[0][i + 1] = true;
                }
            }
            for (int i = 0; i < s.length(); i++) {
                for (int j = 0; j < p.length(); j++) {
                    if (p.charAt(j) == '.') {
                        dp[i + 1][j + 1] = dp[i][j];
                    }
                    if (p.charAt(j) == s.charAt(i)) {
                        dp[i + 1][j + 1] = dp[i][j];
                    }
                    if (p.charAt(j) == '*') {
                        if (p.charAt(j - 1) != s.charAt(i) && p.charAt(j - 1) != '.') {
                            dp[i + 1][j + 1] = dp[i + 1][j - 1];
                        } else {
                            dp[i + 1][j + 1] = (dp[i + 1][j] || dp[i][j + 1] || dp[i + 1][j - 1]);
                        }
                    }
                }
            }
            return dp[s.length()][p.length()];
        }
    }

    public static void main(String[] args) {
        RegularExpressionMatching10 r = new RegularExpressionMatching10();
        Map<String, String> map = new LinkedHashMap<>();
        map.put("b", ".*..b");//false
        map.put("", "aaaa");//false
        map.put("a", "aaaa");//false
        map.put("aa", "a");//false
        map.put("bb", "b*");//true
        map.put("ab", ".*");//true
        map.put("aab", "c*a*b");//true
        map.put("mississippi", "mis*is*p*.");//false
//        map.put("mississippj", "mis*is*i*p*.");//true
        map.put("aaa", "ab*ac*a");//true
        Solution solution = new Solution();
        map.forEach((s, p) -> {
            try {
//                System.out.println(s + "\t" + s.substring(0, s.length()));
                System.out.println("s = " + s + "\t p = " + p + "\t: " + r.isMatchDP(s, p));
                System.out.println("s = " + s + "\t p = " + p + "\t: " + solution.isMatch(s, p));
                System.out.println();

//                if (r.isMatch(s, p) != solution.isMatch(s, p)) {
//                    System.out.println("11111s = " + s + "\t p = " + p);
//                }
            } catch (Throwable e) {
                System.err.println(s + "\t" + p);
                e.printStackTrace();
                throw new RuntimeException();
            }
        });
    }


    //DP

}
